#ifndef _NUMBER_
#define _NUMBER_

#include <algorithm>
#include <math.h>
#include <queue>
#include <regex>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Number {
public:
    Number( /* args */ ) {

        unordered_map< char, int > statusStart  = { { 'b', 0 }, { 's', 1 }, { 'n', 2 }, { 'o', 3 } };
        unordered_map< char, int > statusSymbol = { { 'b', 3 }, { 's', 3 }, { 'n', 2 }, { 'o', 3 } };
        unordered_map< char, int > statusNumber = { { 'b', 3 }, { 's', 3 }, { 'n', 2 }, { 'o', 3 } };
        // unordered_map< char, int > statusEnd    = { { 'b', 3 }, { 's', 3 }, { 'n', 3 }, { 'o', 3 } };

        status.push_back( statusStart );
        status.push_back( statusSymbol );
        status.push_back( statusNumber );
        status.push_back( unordered_map< char, int >{ { 'b', 3 }, { 's', 3 }, { 'n', 3 }, { 'o', 3 } } );
    }
    ~Number() {}

    int strToInt( string str ) {

        size_t len = str.size();
        if ( len == 0 ) {
            return 0;
        }

        int    minusflag = 1;
        size_t i         = 0;
        char   c         = str[ i ];

        while ( c == ' ' ) {
            if ( len == ++i ) {
                return 0;
            }
            c = str[ i ];
        }

        if ( c == '-' ) {
            minusflag = false;
        }

        if ( c == '+' || c == '-' ) {
            ++i;
        }

        int result = 0;

        for ( size_t j = i; j < len; j++ ) {
            char a = str[ j ];
            if ( a < '0' || a > '9' ) {
                break;
            }
            // INT32_MAX = 2147483640 + 7
            if ( result > ( INT32_MAX / 10 ) || ( result == INT32_MAX / 10 && a > '7' ) ) {
                return minusflag == 1 ? INT32_MAX : INT32_MIN;
            }
            result *= 10;
            result += ( a - '0' );
        }

        return minusflag == 1 ? result : -result;
    }
    /*  状态机解法：st为当前状态，用hash表类型的数组存储状态转换表，超出范围return
     *  四个状态：0：开始，1：正负号，2：数字部分，3：结束，
     *  b:blank空格，s：sign + -号，n：数字0-9，o：other其他字符。*
     *  */
    int strToIntStatus( string str ) {

        char   a, c;
        size_t st     = 0;
        int    result = 0, minusflag = 1;

        for ( size_t i = 0; i < str.size(); i++ ) {
            a = str[ i ];
            if ( a == ' ' ) {
                c = 'b';
            }
            else if ( a == '-' || a == '+' ) {
                c = 's';
            }
            else if ( a >= '0' && a <= '9' ) {
                c = 'n';
            }
            else {
                c = 'o';
            }

            st = status[ st ][ c ];
            switch ( st ) {
            case 0:
                break;
            case 1:
                minusflag = ( a == '+' ? 1 : -1 );
                break;
            case 2:
                // 判断边界
                if ( result > ( INT32_MAX / 10 ) || ( result == INT32_MAX / 10 && a > '7' ) ) {
                    return minusflag == 1 ? INT32_MAX : INT32_MIN;
                }
                result *= 10;
                result += a - '0';
                break;
            default:
                return result * minusflag;
            }
        }

        return result * minusflag;
    }

    /*在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。*/
    int singleNumber( vector< int >& nums ) {
        unordered_map< int, bool > imap;
        for ( size_t i = 0; i < nums.size(); i++ ) {
            pair< unordered_map< int, bool >::iterator, bool > r = imap.insert( make_pair< int, bool >( int( nums[ i ] ), false ) );
            if ( r.second == false ) {
                r.first->second = true;
            }
        }
        for ( auto& a : imap ) {
            if ( a.second == false ) {
                return a.first;
            }
        }
        return -1;
    }

    // 剑指 Offer 56 - I. 数组中数字出现的次数 : 位运算
    vector< int > singleNumbers( vector< int >& nums ) {
        int x = 0, y = 0;
        int m = 1, n = 0;
        // 求 x异或y
        for ( auto num : nums ) {
            n ^= num;
        }
        // 从右往左，找到x与y的第一个不同的位数
        while ( ( n & m ) == 0 ) {
            m = m << 1;
        }
        for ( auto num : nums ) {
            if ( ( num & m ) == 0 ) {
                x ^= num;
            }
            else {
                y ^= num;
            }
        }
        return vector< int >{ x, y };
    }

    // 快速幂递归法
    double myPow( double x, int n ) {
        if ( n == 0 ) {
            return 1;
        }
        else if ( n == 1 ) {
            return x;
        }
        else if ( n == -1 ) {
            return 1 / x;
        }

        double ans;

        if ( n % 2 == 0 ) {
            ans = myPow( x, n / 2 );
            ans *= ans;
        }
        else {
            if ( n > 0 ) {
                ans = myPow( x, n - 1 ) * x;
            }
            else {
                ans = myPow( x, n + 1 ) / x;
            }
        }
        return ans;
    }
    // 快速幂迭代法求解，二进制
    double myPow2( double x, int n ) {
        double    ans = 1;
        long long N   = n;
        if ( n > 0 ) {
            while ( N ) {
                if ( N & 1 ) {
                    ans *= x;
                }
                x *= x;
                N >>= 1;
            }
        }
        else {
            N = -N;
            while ( N ) {
                if ( N & 1 ) {
                    ans /= x;
                }
                x *= x;
                N >>= 1;
            }
        }
        return ans;
    }
    /*剑指 Offer 20. 表示数值的字符串。请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。*/
    bool isNumber( string s ) {

        regex reg( "\\s*[+-]?((\\d*\\.\\d+)|(\\d+\\.\\d*|(\\d+))){1}([eE][+-]?\\d+)?\\s*" );
        return std::regex_match( s, reg );
    }

    /* 剑指 Offer 66. 构建乘积数组
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
     * 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。*/
    vector< int > constructArr( vector< int >& a ) {
        int           len = a.size();
        vector< int > ans( len );
        if ( len == 0 ) {
            return ans;
        }
        ans[ 0 ] = 1;
        for ( int i = 1; i < len; i++ ) {
            ans[ i ] = ans[ i - 1 ] * a[ i - 1 ];
        }
        int R = a[ len - 1 ];
        for ( int i = len - 2; i >= 0; i-- ) {
            ans[ i ] *= R;
            R *= a[ i ];
        }
        return ans;
    }

    /* 剑指 Offer 17. 打印从1到最大的n位数 */
    vector< int > printNumbers( int n ) {
        int num = 1;
        for ( int i = 0; i < n; i++ ) {
            num *= 10;
        }
        num -= 1;

        vector< int > ans( num );

        for ( int i = 1; i <= num; i++ ) {
            ans[ i - 1 ] = i;
        }
        return ans;
    }

    /* 剑指 Offer 15. 二进制中1的个数 */
    int hammingWeight( uint32_t n ) {
        int ans = 0;
        while ( n != 0 ) {
            if ( n & 1 ) {
                ans++;
            }
            n = n >> 1;
        }
        return ans;
    }

    /* 剑指 Offer 61. 扑克牌中的顺子 */
    bool isStraight( vector< int >& nums ) {
        if ( nums.size() != 5 ) {
            return false;
        }
        sort( nums.begin(), nums.end() );
        int king  = 0;
        int front = 0, minus = -1;
        for ( auto it = nums.begin(); it != nums.end(); it++ ) {

            if ( ( *it ) == 0 ) {
                king++;
            }
            else {
                if ( front != 0 ) {
                    minus = ( *it ) - front;
                    if ( minus == 0 ) {
                        return false;
                    }
                    else if ( minus != 1 ) {
                        if ( minus - 1 > king ) {
                            return false;
                        }
                        king -= minus - 1;
                    }
                }
                front = *it;
            }
        }
        return true;
    }

    /* 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。
     * 数组排序法： 将数组 nums 排序，数组(中点)的元素 一定为众数。
     * 摩尔投票法： 核心理念为 票数正负抵消。 此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法
     */
    int majorityElement( vector< int >& nums ) {

        int len = nums.size();
        if ( len <= 0 ) {
            return 0;
        }
        int ans = 0, votes = 0;

        for ( size_t i = 0; i < nums.size(); i++ ) {
            if ( votes == 0 ) {
                ans = nums[ i ];
            }
            votes += nums[ i ] == ans ? 1 : -1;
        }
        // 若没有这样的数
        int count = 0;
        for ( size_t i = 0; i < nums.size(); i++ ) {
            count += nums[ i ] == ans ? 1 : 0;
        }
        return count > len / 2 ? ans : 0;
    }

    /* 剑指 Offer 57. 和为s的两个数字
     * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。*/
    vector< int > twoSum( vector< int >& nums, int target ) {
        int           len = nums.size();
        vector< int > ans( 2 );
        int           i = 0, j = len - 1;
        while ( i <= j ) {
            if ( target - nums[ i ] == nums[ j ] ) {
                ans[ 0 ] = nums[ i ];
                ans[ 1 ] = nums[ j ];
                break;
            }
            else if ( target - nums[ i ] < nums[ j ] ) {
                j--;
            }
            else if ( target - nums[ i ] > nums[ j ] ) {
                i++;
            }
        }
        return ans;
    }

    /* 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 */
    vector< int > exchange( vector< int >& nums ) {
        int len = nums.size();
        int i = 0, j = len - 1, temp;

        while ( i <= j ) {
            if ( nums[ i ] % 2 == 0 && nums[ j ] % 2 != 0 ) {
                temp      = nums[ i ];
                nums[ i ] = nums[ j ];
                nums[ j ] = temp;
                i++;
                j--;
            }
            else if ( nums[ i ] % 2 == 0 && nums[ j ] % 2 == 0 ) {
                j--;
            }
            else if ( nums[ i ] % 2 != 0 && nums[ j ] % 2 != 0 ) {
                i++;
            }
            else {
                i++;
                j--;
            }
        }
        return nums;
    }

    /* 剑指 Offer 40. 最小的k个数 1.优先队列 2. 快排*/
    vector< int > getLeastNumbers( vector< int >& arr, int k ) {
        vector< int > ans( k, -1 );
        if ( k == 0 ) {
            return ans;
        }
        priority_queue< int, vector< int >, less< int > > qu;  // 默认大顶堆    greater / less
        for ( size_t i = 0; i < arr.size(); i++ ) {
            if ( qu.size() < size_t( k ) ) {
                qu.push( arr[ i ] );
            }
            else if ( arr[ i ] < qu.top() ) {
                qu.pop();
                qu.push( arr[ i ] );
            }
        }
        for ( int i = 0; i < k; i++ ) {
            ans[ i ] = qu.top();
            qu.pop();
        }
        return ans;
    }

    vector< int > getLeastNumbers2( vector< int >& arr, int k ) {
        if ( k == 0 ) {
            return vector< int >();
        }
        else if ( size_t( k ) >= arr.size() ) {
            return arr;
        }

        return quickSort( arr, 0, arr.size() - 1, k );
    }

    vector< int > quickSort( vector< int >& arr, int begin, int end, int k ) {

        int pivot = arr[ begin ];
        int i = begin, j = end;

        while ( i < j ) {
            while ( i < j && arr[ j ] >= pivot ) {
                j--;
            }
            while ( i < j && arr[ i ] <= pivot ) {
                i++;
            }
            swap( arr[ i ], arr[ j ] );
        }
        swap( arr[ begin ], arr[ i ] );  // i == j
        if ( i < k ) {
            return quickSort( arr, i + 1, end, k );
        }
        else if ( i > k ) {
            return quickSort( arr, begin, i - 1, k );
        }

        vector< int > ans( k );
        ans.assign( arr.begin(), arr.begin() + k );
        return ans;
    }
    /* 剑指 Offer 42. 连续子数组的最大和
    输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n) */
    int maxSubArray( vector< int >& nums ) {
        int len = nums.size();
        if ( len <= 0 ) {
            return 0;
        }
        int dp = INT16_MIN;
        int dpN;
        int ans = INT16_MIN;
        for ( int i = 0; i < len; ++i ) {
            dpN = max( dp + nums[ i ], nums[ i ] );
            ans = max( ans, dpN );
            dp  = dpN;
        }
        return ans;
    }

    /* 剑指 Offer 51. 数组中的逆序对 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。(hard)
     * tips: 归并排序 O(n) = nlogn */
    int reversePairs( vector< int >& nums ) {
        vector< int > temp( nums.size() );
        return mergeSort( nums, 0, nums.size() - 1, temp );
    }

    int mergeSort( vector< int >& nums, int l, int r, vector< int >& tmp ) {
        // 终止条件
        if ( l >= r ) {
            return 0;
        }

        // 划分
        int mid = l + ( ( r - l ) >> 1 );
        int ans = mergeSort( nums, l, mid, tmp ) + mergeSort( nums, mid + 1, r, tmp );

        // 归并
        int i = l, j = mid + 1;  // i、j 分别为两个数组的起始位置

        for ( int k = l; k <= r; k++ ) {  // 记录原始数据
            tmp[ k ] = nums[ k ];
        }

        for ( int k = l; k <= r; k++ ) {
            if ( i == mid + 1 ) {  // 第一个数组遍历完毕
                nums[ k ] = tmp[ j++ ];
            }
            else if ( j == r + 1 ) {  // 第二个数组遍历完毕
                nums[ k ] = tmp[ i++ ];
            }
            else if ( tmp[ i ] <= tmp[ j ] ) {  // 递增序列 第一个数组指针右移
                nums[ k ] = tmp[ i++ ];
            }
            else {  // tmp[ i ] > tmp[ j ] 逆序：第二个数组指针右移
                nums[ k ] = tmp[ j++ ];
                ans += mid - i + 1;
            }
        }

        return ans;
    }
    // 剑指 Offer 45. 把数组排成最小的数
    string minNumber( vector< int >& nums ) {
        string           result;
        vector< string > strs;

        for ( size_t i = 0; i < nums.size(); i++ ) {
            strs.push_back( std::to_string( nums[ i ] ) );
        }

        std::sort( strs.begin(), strs.end(), []( string s1, string s2 ) { return s1 + s2 < s2 + s1 ? true : false; } );

        for ( size_t i = 0; i < strs.size(); i++ ) {
            result += strs[ i ];
        }
        return result;
    }

    // 349. 两个数组的交集:给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是唯一的,不考虑输出结果的顺序
    // 方法一：两个集合 ; 方法二：排序 + 双指针
    vector< int > intersection( vector< int >& nums1, vector< int >& nums2 ) {

        std::sort( nums1.begin(), nums1.end() );
        std::sort( nums2.begin(), nums2.end() );

        size_t        i = 0, j = 0;
        vector< int > result;

        while ( i < nums1.size() && j < nums2.size() ) {
            if ( nums1[ i ] == nums2[ j ] ) {
                // 唯一性
                if ( result.empty() || result.back() != nums1[ i ] ) {
                    result.push_back( nums1[ i ] );
                }
                i++;
                j++;
            }
            else if ( nums1[ i ] < nums2[ j ] ) {
                i++;
            }
            else if ( nums1[ i ] > nums2[ j ] ) {
                j++;
            }
        }
        return result;
    }

    // 15. 三数之和
    vector< vector< int > > threeSum( vector< int >& nums ) {
        vector< vector< int > > result;
        if ( nums.empty() ) {
            return result;
        }
        std::sort( nums.begin(), nums.end() );
        int len = nums.size();

        for ( int i = 0; i < len - 2; i++ ) {
            if ( nums[ i ] > 0 ) {
                return result;
            }
            if ( i > 0 && nums[ i - 1 ] == nums[ i ] ) {
                continue;
            }
            int L = i + 1, R = len - 1;
            while ( L < R ) {
                int sum = nums[ i ] + nums[ L ] + nums[ R ];
                if ( sum == 0 ) {
                    result.push_back( vector< int >{ nums[ i ], nums[ L ], nums[ R ] } );
                    while ( L < R && nums[ L ] == nums[ L + 1 ] ) {
                        L++;
                    }
                    while ( L < R && nums[ R ] == nums[ R - 1 ] ) {
                        R--;
                    }
                }
                else {
                    sum < 0 ? L++ : R--;
                }
            }
        }
        return result;
    }

    // 剑指 Offer 57 - II. 和为s的连续正数序列
    vector< vector< int > > findContinuousSequence( int target ) {
        vector< vector< int > > result;

        int limit = floor( target / 2 );  // 下取整 floor( target / 2 ) == (target -1) /2
        for ( long long i = 1; i <= limit; i++ ) {
            long long delta = 1 - ( 4 * ( i - i * i - 2 * target ) );
            double    s     = sqrt( delta );
            if ( delta >= 0 && ( s == floor( s ) ) ) {
                int x1 = -1 + int( s );
                if ( x1 > 0 && x1 % 2 == 0 ) {
                    x1 /= 2;
                    vector< int > temp;
                    for ( int k = i; k <= x1; k++ ) {
                        temp.push_back( k );
                    }
                    result.push_back( temp );
                }
            }
        }

        return result;
    }

    // 不用 + 号算加法： 进位 + 非进位 （& ^）
    int add( int a, int b ) {
        while ( b != 0 ) {
            int tempSum  = a ^ b;
            int carrySum = ( a & b ) << 1;

            a = tempSum;
            b = carrySum;
        }
        return a;
    }

private:
    vector< unordered_map< char, int > > status;
};
#endif
